package leetcode100

// TODO 脑筋急转弯 | 快慢指针 【-】 寻找重复数
// TODO https://leetcode.cn/problems/find-the-duplicate-number/solution/zhe-ge-shu-zu-you-dian-te-shu-suo-yi-ke-yi-yong-ku/

func findDuplicate(nums []int) int {
	slow, fast := 0, 0
	for {
		slow = nums[slow]
		fast = nums[nums[fast]]  // slow跳一步，fast跳两步

		if slow == fast {    // 指针首次相遇
			fast = 0         // 让快指针回到起点
			for {            // 开启新的循环
				if slow == fast {    // 如果再次相遇，就肯定是在入口处
					return slow      // 返回入口，即重复的数
				}
				slow = nums[slow]    // 两个指针每次都进1步
				fast = nums[fast]
			}
		}
	}
}